package ljl.codetop300;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 堆排序？不可能自己写的，直接优先队列
 *
 * 错了，这个题让找最小的 k 个数，没让这 k 个数有序，明明是在考察 "快速选择排序"
 *
 */
public class _offer_40 {

  public int[] getLeastNumbers(int[] arr, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (int i : arr) {
      q.offer(i);
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
      res[i] = q.poll();
    }
    return res;
  }

  /**
   * 不知道为什么我这个性能很差，比上面的还差
   */
  static class quick_select {

    public static void main(String[] args) {
      int[] s = new quick_select().getLeastNumbers(new int[]{5, 4, 3, 2, 1}, 3);
      System.out.println(Arrays.toString(s));
    }

    public int[] getLeastNumbers(int[] arr, int k) {
      quickSelect(arr, 0, arr.length - 1, k);
      return Arrays.copyOf(arr, k);
    }

    void quickSelect(int[] arr, int from, int to, int k) {
      if (from >= to) return;
      int p = arr[from];
      int l = from;
      int r = to;
      while (l < r) {
        while (l < r && arr[r] >= p) r--;
        arr[l] = arr[r];
        while (l < r && arr[l] <= p) l++;
        arr[r] = arr[l];
      }
      arr[l] = p;
      if (l < k) quickSelect(arr, l + 1, to, k);
      else if (l > k) quickSelect(arr, from, l - 1, k);
    }
  }

  static class lu_fei {
    public int[] getLeastNumbers(int[] arr, int k) {
      if (k >= arr.length) return arr;
      return quickSort(arr, k, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
      int i = l, j = r;
      while (i < j) {
        while (i < j && arr[j] >= arr[l]) j--;
        while (i < j && arr[i] <= arr[l]) i++;
        swap(arr, i, j);
      }
      swap(arr, i, l);
      if (i > k) return quickSort(arr, k, l, i - 1);
      if (i < k) return quickSort(arr, k, i + 1, r);
      return Arrays.copyOf(arr, k);
    }
    private void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
  }
}
